﻿#include "SeqList.h"
//初始化动态顺序表
void SlInit(SL* ps)//结构体指针
{
	//都初始化为没有先
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

//顺序表的销毁
void SlDestroy(SL* ps)
{
	if (ps->arr != NULL)
	{
		//不为空，则释放
		free(ps->arr);
	}
	//然后回到初始化一样
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}
//插入数据之前先看空间够不够
void SlCheckCapacity(SL* ps)
{
	//三目表达式
	//一开始空间为0,就赋4，之后空间不够了，就扩充2倍，依次——
	int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
	//申请多大空间
	SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
	//申请失败
	if (tmp == NULL)
	{
		perror("realloc fail");
		exit(1);
	}
	//申请成功
	ps->arr = tmp;
	ps->capacity = newCapacity;
}
//尾插
void SlPushBack(SL* ps, SLDataType x)		//x表示要插入的
{
	//if (ps == NULL)
	//{
	//	return 1;
	//}
	assert(ps);
	//空间检查函数：插入数据之前先看空间够不够
	SlCheckCapacity(ps);
	//开始插呗（从后面插）
	ps->arr[ps->size] = x;
	ps->size++;		//数据个数加1
}
//头插
void SlPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	//空间检查函数：插入数据之前先看空间够不够
	SlCheckCapacity(ps);
	//开始插呗
	//已经有的数据都往后移动一位
	int i = 0;
	for (i = ps->size; i >= 1; i--)
	{
		//i一开始是ps->size，是i的初始化值
		//i-1最小为0，所以i>=1或者i>0,这是判断条件
		ps->arr[i] = ps->arr[i - 1];
	}
	//插入
	ps->arr[0] = x;
	//有效数据个数加1
	ps->size++;
}
//打印数据
void SLPrint(SL s)
{
	int i = 0;
	for (i = 0; i < s.size; i++)
	{
		printf("%d ", s.arr[i]);
	}
	printf("\n");
}
//尾删
void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->arr);
	//顺序表不为空
	//方法1-把那些数据改为-1
	//ps->arr[ps->size - 1] = -1;
	//方法2-size-1(有效数据个数-1)
	ps->size--;
}
//头删
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->arr);
	//后面的往前覆盖
	int i = 0;
	for (i = 0; i < ps->size - 1; i++)
	{
		//0<-1  1<-2  2<-3    size-1<-size  
		//所以i初始值为0，判断条件为i<=size-2
		ps->arr[i] = ps->arr[i + 1];
	}
	//有效数据个数减少一个
	ps->size--;
}
//指定位置之前插⼊
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	//判断输入位置是否合理
	assert(pos >= 0 && pos <= ps->size);		//这里size能等
	//空间检查函数：插入数据之前先看空间够不够
	SlCheckCapacity(ps);
	//在这个位置之后的数据往后挪动一位，空出一个位置插入
	int i = 0;
	for (i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];		//pos-1=pos-2
	}
	//插入
	ps->arr[pos] = x;
	//数据个数加1
	ps->size++;
}
//删除指定位置的数据
void SLErase(SL* ps, int pos)
{
	assert(ps);
	//判断输入位置是否合理
	assert(pos >= 0 && pos < ps->size);		//这里size不能等
	//开始覆盖就行
	int i = 0;
	for (i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];			//size-2=size-1
	}
	//数据减少一个
	ps->size--;
}
//查找
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			//返回下标
			return i;		//非负数（0-ps->size）
		}
	}
	//没有找到
	return -1;
}